"""
quicksort_v4
三向切分改进，大于pivot值时会先移动gt指针，直到第一个不大于pivot值的位置，再进行交换
"""
import random
import sys
sys.setrecursionlimit(1100000)  # 将默认的递归深度修改为1100000


def rand_partition_v4_1(sequence, p, r):
    i = random.randint(p, r)
    sequence[p], sequence[i] = sequence[i], sequence[p]
    x = sequence[p]
    lt = p
    gt = r
    i = p + 1
    while i <= gt:
        if sequence[i] < x:
            sequence[lt], sequence[i] = sequence[i], sequence[lt]
            lt += 1
            i += 1
        elif sequence[i] > x:
            while sequence[gt] > x and i <= gt:
                gt -= 1
            if i < gt:
                sequence[i], sequence[gt] = sequence[gt], sequence[i]
                gt -= 1
        else:
            i += 1

    return lt, gt


def _quicksort_v4_1(sequence, p, r):
    if p < r:
        lt, gt = rand_partition_v4_1(sequence, p, r)
        _quicksort_v4_1(sequence, p, lt - 1)
        _quicksort_v4_1(sequence, gt + 1, r)


def quicksort_v4_1(sequence):
    _quicksort_v4_1(sequence, 0, len(sequence) - 1)


if __name__ == '__main__':
    import os
    import time
    from dataset import load_dataset
    from utils import is_ordered

    s = load_dataset(os.path.join('datasets', 'dataset-1.txt'))
    # s = list(range(10))
    # s = [7, 8, 9, 5, 1, 4, 2, 3, 6, 0]
    # random.shuffle(s)
    # print('s:', s)
    start = time.time()
    quicksort_v4_1(s)
    elapsed = time.time() - start
    # print('sorted s:', s)
    print('sort success')
    print('consume:', elapsed)
    print('is ordered:', is_ordered(s))
